package com.fth.learn.chapter04;

import java.util.Arrays;

/**
 * 快排
 * YiMi
 *
 * @author YiMi
 * @version 1.0
 * @date 2023/5/27 9:34
 */

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {10,13,2,4,5,9,11,1,6,7,19,34};
        int middle = arr.length >>1;
        int left = 0;
        int right = arr.length - 1;


        while (true){
            //首先找到left对应的数据大于middel
            while (right>left && arr[left] < arr[middle]){
                left++;
            }
            //找到right 对应的数据小于middel
            while (right>left && arr[right] > arr[middle]){
                right--;
            }
            if(right <= left){
                break;
            }

            arr[right] = arr[right] + arr[left];
            arr[left] = arr[right] - arr[left];
            arr[right] = arr[right] - arr[left];

        }
        System.out.println(Arrays.toString(arr));
//老师写的

//        int[] arr = {4, 2, 1, 10, 6, 3, 7, 8, 9};
////        quickRow(arr,0,arr.length-1);
////        System.out.println(Arrays.toString(arr));
//        int middle = arr[0];
//        int left = 0 + 1;
//        int right = arr.length - 1;
//
//        while (left < right) {
//
//            //交换 两个下标 (一个大于left middle  小于right middle)
//            //首先找到left对的应的数据 大于middle
//            while (arr[left] <= middle && left < right) {
//                left++;
//            }
//
//            //left 表示上面的while不走了，第一个大于middle的数的下标
//            // 再找到right 对应的数据 小于middle
//            while (arr[right] >= middle && left < right) {
//                right--;
//            }
//
//            if (left < right) {
//                //交换swap(left,right)
//                int temp = arr[right];
//                arr[right] = arr[left];
//                arr[left] = temp;
//            }
//        }
//        //现在的左右
//        System.out.println(left + "||" + right);
//        System.out.println(Arrays.toString(arr));
//        arr[0] = arr[left];
//        arr[left] = middle;
//        System.out.println(Arrays.toString(arr));

//        public class QuickSort {
//
//            public static void main(String[] args) {
//                int[] array = {4, 3, 2, 5, 1, 7, 8, 9};
//                quickRow(array, 0, array.length - 1);
//                System.out.println(Arrays.toString(array));
//            }
//
//            /**
//             * 快排
//             * @param array 数组
//             * @param low   开始
//             * @param high  最大元素
//             */
//            public static void quickRow(int[] array, int low, int high) {
//                /**
//                 * i 表示左侧
//                 * j 表示右侧
//                 * pivot 标准 (可不可以是中间，可以不可以是0 )
//                 */
//                int i, j, pivot;
//
//                if (low >= high) {
//                    return;
//                }
//                // 左侧从哪里开始  0
//                i = low;
//                //右侧从哪里开始   array.length-1
//                j = high;
//                //现在我们的标准是 0
//                pivot = array[low];
//                while (i < j) {
//                    //右侧
//                    while (array[j] >= pivot && i < j) {
//                        j--;
//                    }
//                    //从左向右
//                    while (array[i] <= pivot && i < j) {
//                        i++;
//                    }
//
//                    if (i < j) {
//                        int temp = array[i];
//                        array[i] = array[j];
//                        array[j] = temp;
//                    }
//                }
//                //交换标准
//                array[low] = array[i];
//                array[i] = pivot;
//                quickRow(array, low, i - 1);
//                quickRow(array, i + 1, high);
//            }


//        }
    }
}
